package basic.basic_class02;

/**
 * 马拉车算法应用实列：
 * 题目描述：给定一个字符串，向字符串后面添加最短的字符串，使其成为回文字符串
 *
 * 思路：
 * 	1. 按照马拉车算法的思想，一直计算最大右边界的停靠位置
 * 	2. 一旦右边界到达了最后一个元素的位置时，停止
 * 	3. 向前找到左边界
 * 	4. 将左边界左边的元素逆序加到右边界后面即可
 *
 */
public class Code_05_Manacher_ShortestEnd {

	public static char[] manacherString(String str) {
		char[] charArr = str.toCharArray();
		char[] res = new char[str.length() * 2 + 1];
		int index = 0;
		for (int i = 0; i != res.length; i++) {
			res[i] = (i & 1) == 0 ? '#' : charArr[index++];
		}
		return res;
	}

	public static String shortestEnd(String str) {
		if (str == null || str.length() == 0) {
			return null;
		}
		char[] charArr = manacherString(str);
		int[] pArr = new int[charArr.length];
		int index = -1;
		int pR = -1;
		int maxContainsEnd = -1;
		for (int i = 0; i != charArr.length; i++) {
			pArr[i] = pR > i ? Math.min(pArr[2 * index - i], pR - i) : 1;
			while (i + pArr[i] < charArr.length && i - pArr[i] > -1) {
				if (charArr[i + pArr[i]] == charArr[i - pArr[i]])
					pArr[i]++;
				else {
					break;
				}
			}
			if (i + pArr[i] > pR) {
				pR = i + pArr[i];
				index = i;
			}
			if (pR == charArr.length) {
				maxContainsEnd = pArr[i];
				break;
			}
		}
		char[] res = new char[str.length() - maxContainsEnd + 1];
		for (int i = 0; i < res.length; i++) {
			res[res.length - 1 - i] = charArr[i * 2 + 1];
		}
		return String.valueOf(res);
	}

	public static String shortestEnd2(String s) {
		// 首先将字符串加上虚轴
		char[] chars = new char[s.length() * 2 + 1];
		int n = chars.length;
		for (int i = 0; i < n; i++) {
			chars[i] = i % 2 == 0 ? '#' : s.charAt(i/2);
		}
		// 创建记录最大回文半径的数组, 最大回文右边界和回文中心
		int[] radius = new int[n];
		int R = -1;
		int C = -1;
		int maxLeft = -1;
		for (int i = 0; i < n; i++) {
			radius[i] = R > i ? Math.min(R - i, radius[2*C-i]) : 1;
			// 进行中心扩展
			while(i + radius[i] < n && i - radius[i] >= 0) {
				if(chars[i - radius[i]] == chars[i + radius[i]]){
					radius[i]++;
				}else{
					break;
				}
			}
			// 更新最大回文半径
			if(i + radius[i] > R){
				R = i + radius[i];
				C = i;
			}
			if(R == n){
				maxLeft = radius[i];
				break;
			}
		}
		StringBuilder res = new StringBuilder();
		for (int i = maxLeft; i >= 0; i--) {
			if(chars[i] != '#'){
				res.append(chars[i]);
			}
		}
		return res.toString();
	}

	public static void main(String[] args) {
		String str2 = "abcd123321";
		System.out.println(shortestEnd2(str2));

	}

}
